n=1000;
m=326;
road=[|43,37,183|
760,571,207|
729,521,195|
368,470,7077|
812,959,241|
595,154,9584|
894,417,4367|
22,745,7010|
566,456,8824|
689,50,3151|
544,222,1083|
476,916,96|
399,722,9710|
926,319,1246|
783,361,8297|
331,945,5790|
86,986,1623|
152,400,1135|
69,705,3176|
602,486,720|
747,904,3265|
298,977,7754|
324,327,4715|
761,57,728|
750,113,3616|
922,684,9995|
468,522,4017|
588,45,4225|
662,403,8995|
520,871,5358|
174,245,4141|
51,797,942|
785,36,52|
270,527,7333|
399,798,6415|
862,507,7504|
118,442,391|
915,726,8897|
274,935,4936|
56,17,8203|
44,364,1186|
198,107,227|
318,160,4217|
531,628,2532|
730,594,6833|
497,66,3692|
380,681,3171|
619,805,700|
615,237,4106|
630,470,620|
737,474,7415|
592,41,4533|
708,273,1229|
729,575,1893|
779,293,806|
498,695,997|
661,68,28|
360,405,6345|
313,612,3649|
614,458,9148|
132,518,6216|
205,404,9718|
479,541,3865|
189,858,579|
576,826,9169|
703,865,176|
545,924,1040|
907,41,9727|
132,161,2153|
398,218,9271|
497,627,205|
934,107,6489|
139,317,4049|
1,856,1787|
806,573,3595|
981,671,4761|
557,799,4665|
440,955,903|
124,403,1198|
358,836,6848|
619,868,4018|
231,923,692|
198,407,7562|
996,432,1033|
404,889,6830|
897,931,3558|
696,428,7558|
119,436,28|
128,621,836|
998,890,569|
850,225,2438|
914,17,1947|
166,127,2402|
317,573,1022|
955,682,8379|
133,802,455|
828,373,1676|
311,258,3616|
868,72,5366|
981,566,388|
33,172,9133|
511,226,4514|
270,260,2632|
223,814,2972|
262,59,9397|
782,214,6233|
297,728,3154|
450,375,2274|
152,616,7077|
326,363,9863|
137,461,918|
351,145,6280|
333,125,5103|
45,468,7084|
250,686,3843|
20,693,878|
793,823,1172|
688,53,6555|
167,904,8907|
570,940,8885|
111,707,356|
638,563,2115|
890,692,6016|
574,660,5551|
44,559,3377|
646,713,3575|
383,597,9793|
290,283,1228|
980,828,4556|
191,859,888|
16,969,3201|
673,568,691|
30,603,201|
136,217,3089|
402,620,208|
570,168,6052|
74,598,2046|
549,582,7435|
959,421,4879|
303,656,8001|
995,84,1591|
202,42,6676|
359,60,4303|
407,675,37|
638,208,4882|
631,991,8300|
552,736,4656|
337,492,5682|
246,778,9007|
776,323,2997|
199,52,2310|
499,204,4184|
568,808,1072|
692,253,7392|
654,358,5551|
587,996,2072|
243,168,1942|
859,123,878|
63,572,157|
88,103,2548|
140,493,6337|
679,968,1168|
185,969,4769|
614,418,9612|
939,878,3554|
683,963,8806|
133,936,1167|
592,417,9601|
553,171,9516|
680,777,1027|
163,86,4528|
467,902,1017|
853,64,7486|
785,804,1120|
744,896,8540|
801,392,6712|
804,244,8169|
357,648,6145|
723,11,329|
446,852,4891|
326,942,7919|
223,633,813|
451,75,4341|
648,912,7424|
207,390,2161|
725,240,6178|
554,668,6674|
553,16,4439|
144,712,8447|
298,472,5899|
125,339,4221|
423,733,1361|
430,340,8058|
321,785,893|
354,880,6646|
783,499,4095|
743,860,7797|
652,310,6416|
231,233,8462|
112,581,5667|
242,879,1087|
812,997,7295|
781,306,9558|
151,843,156|
15,775,4169|
331,724,4605|
496,742,207|
389,653,9039|
469,607,3429|
876,476,2602|
532,473,779|
886,297,617|
709,137,300|
267,525,9753|
867,299,6169|
647,66,8700|
674,24,670|
19,57,7753|
382,932,7915|
834,678,1050|
651,989,9469|
170,229,442|
181,671,2211|
279,251,531|
562,736,4537|
55,663,5491|
836,120,10000|
50,936,9736|
43,629,142|
342,451,1743|
142,917,6821|
748,450,5418|
949,635,5223|
330,617,6400|
722,585,4722|
925,123,5003|
337,877,5450|
450,207,6041|
491,183,739|
864,705,9195|
131,441,3462|
425,329,4249|
884,31,119|
169,360,3020|
678,221,9614|
770,519,8626|
583,851,6194|
282,185,598|
871,2,6353|
309,4,6805|
892,574,5721|
607,388,3954|
179,506,9696|
442,377,3891|
758,217,561|
430,584,7641|
478,843,4109|
899,695,5020|
304,484,731|
263,87,175|
711,407,5177|
995,526,8467|
958,542,6225|
974,64,5366|
929,96,2084|
813,454,455|
767,719,4834|
308,502,1358|
440,857,9727|
4,703,5882|
46,329,3268|
810,939,479|
580,891,1325|
759,313,4013|
19,458,4073|
719,62,2324|
672,705,5677|
397,203,9200|
14,132,1872|
688,555,4628|
588,401,8080|
139,177,9974|
523,813,8620|
183,364,199|
820,236,2184|
869,512,9134|
230,549,45|
281,725,4741|
906,584,774|
70,89,1962|
512,32,4739|
116,722,4312|
932,774,2346|
993,977,4235|
189,660,3313|
559,721,4920|
161,455,5542|
160,34,192|
694,143,1879|
738,657,9814|
174,873,6346|
126,723,7056|
27,242,250|
997,276,6595|
988,480,7240|
212,177,6773|
539,623,2735|
356,817,1215|
213,295,473|
210,200,8804|
6,191,3492|
2,374,3376|
20,861,2901|
15,653,6604|
686,249,7652|
285,75,9601|
701,257,677|
685,37,1231|
94,465,847|
196,330,6518|
193,488,1924|
250,601,126|
965,201,4749|
844,404,111|
992,350,7984|
906,147,6441|
869,343,7303|
472,344,1534|
342,393,2237|
462,266,2419|
368,158,2562|
431,239,7890|
263,379,9178|
912,205,3371|
674,113,6973|
58,875,4287|
700,982,8728|
323,858,1747|
359,255,43|
206,780,835|
361,623,1049|
834,863,1436|
643,649,1276|
912,957,6529|
595,883,834|
830,117,3271|
690,539,401|
262,727,25|
316,265,999|
756,127,5060|
371,321,7211|
662,355,2380|
13,97,4198|
720,194,4262|
91,627,779|
413,578,3436|
452,26,1308|
945,694,5372|
444,841,2130|
993,887,5433|
410,847,5097|
388,640,2600|
805,879,7857|
995,562,9396|
712,519,4734|
500,780,5115|
60,228,2105|
448,900,907|
356,755,3182|
48,236,9222|
642,990,4396|
195,985,3194|
513,246,1177|
389,786,6313|
954,654,1125|
43,228,2614|
616,534,5485|
445,582,403|
897,286,1618|
433,436,7701|
350,815,9663|
884,954,3423|
992,199,6425|
44,506,727|
838,73,5934|
47,457,641|
494,841,286|
320,395,1065|
921,536,8956|
176,125,9428|
718,691,925|
315,31,1433|
820,490,494|
300,792,8563|
584,447,3589|
216,901,971|
100,599,6072|
27,247,7040|
578,156,6890|
274,615,4180|
870,208,9128|
792,789,3949|
290,15,1425|
382,122,9766|
578,524,9562|
528,579,956|
42,462,7115|
947,564,683|
188,164,2816|
822,653,7612|
357,689,4169|
238,8,5494|
657,488,1419|
366,874,2079|
606,346,9212|
646,680,839|
517,599,6539|
274,190,2357|
983,593,2614|
53,30,4372|
9,522,4802|
546,54,1537|
509,994,2358|
978,608,6046|
377,872,782|
945,102,4306|
329,244,2623|
610,855,4663|
487,272,1527|
987,580,9306|
739,726,7152|
541,336,8655|
354,850,7607|
369,971,7914|
535,823,2300|
360,438,9831|
558,799,4834|
648,626,4707|
420,384,988|
230,227,5104|
990,222,4073|
983,740,7558|
406,596,6581|
187,520,2812|
720,103,3852|
12,984,4899|
184,61,4725|
774,256,6588|
425,136,765|
617,150,106|
518,151,5347|
594,369,3311|
979,671,9948|
541,352,1004|
665,967,134|
835,87,4088|
572,165,4731|
858,834,5334|
960,747,717|
465,182,6103|
913,242,7738|
555,2,1117|
917,574,347|
201,523,4414|
424,89,8971|
622,76,7820|
206,487,6363|
856,758,5437|
514,921,1311|
877,736,2319|
808,709,2127|
454,16,707|
209,631,754|
453,800,9317|
619,475,2662|
190,368,5288|
755,347,7122|
184,702,6637|
637,81,6018|
18,8,8198|
915,557,2483|
700,540,9929|
696,925,2165|
693,577,3376|
172,320,1915|
655,456,2761|
536,275,7615|
543,38,8551|
265,981,8139|
538,634,9296|
970,411,698|
919,623,9165|
476,497,7635|
921,293,6957|
115,918,7515|
609,788,8786|
346,530,613|
520,112,752|
162,41,3840|
940,181,2344|
159,238,1985|
435,714,63|
978,548,5856|
332,840,7167|
164,596,2345|
257,291,5944|
70,821,2636|
511,691,4024|
503,66,4157|
815,215,5691|
842,149,549|
908,930,1160|
855,771,8207|
772,140,1130|
924,237,2540|
192,267,1205|
911,618,1234|
661,800,3205|
716,810,2626|
508,474,947|
659,211,7952|
598,854,4526|
881,803,3913|
372,328,8664|
745,554,3265|
398,109,22|
98,438,7184|
903,101,6716|
124,504,6403|
456,311,2574|
258,384,1305|
319,900,7064|
501,36,8024|
768,669,8263|
700,847,1686|
408,13,957|
94,787,1568|
817,751,8481|
710,942,4023|
681,175,3837|
472,911,9773|
778,84,527|
804,35,8540|
862,459,7256|
449,34,8224|
168,635,6944|
395,754,1160|
427,523,2432|
166,151,5385|
237,182,838|
196,698,7931|
288,511,3860|
755,219,5274|
106,704,2194|
163,866,3174|
966,918,2056|
814,506,9379|
699,58,4388|
928,156,3162|
386,596,1946|
138,814,4806|
149,632,5983|
806,794,1624|
415,829,8877|
881,589,5060|
956,821,4274|
632,824,3425|
106,577,7073|
907,365,6621|
962,394,5391|
815,684,8870|
661,64,3127|
379,831,1490|
710,752,7719|
280,324,281|
521,29,6033|
481,221,9174|
888,832,7659|
429,964,2905|
537,6,8159|
618,313,5511|
162,658,3052|
569,434,6585|
926,586,2387|
763,644,8569|
415,946,2458|
119,886,7736|
941,764,2332|
897,962,7211|
319,833,7575|
579,595,3849|
585,910,237|
522,480,6926|
122,99,553|
639,345,1092|
760,570,903|
61,516,5205|
923,507,3282|
62,990,2241|
882,139,8634|
676,426,2254|
244,11,3250|
5,894,3755|
238,895,8535|
136,464,8589|
325,558,7429|
477,189,1402|
764,639,9807|
626,7,3856|
263,363,5259|
353,158,9695|
463,887,4148|
478,709,7947|
195,913,2086|
591,971,1043|
38,742,5526|
536,741,4349|
352,330,200|
419,690,5248|
129,636,598|
146,24,8679|
688,20,4335|
807,934,413|
284,524,3638|
769,801,6636|
21,104,5359|
220,920,748|
65,229,7702|
346,273,4970|
81,994,40|
154,345,3767|
895,49,7559|
550,666,517|
230,537,4986|
23,757,7077|
865,794,4747|
899,952,9532|
842,883,517|
843,448,3953|
93,98,460|
517,716,966|
266,482,9088|
77,197,1818|
733,603,1233|
633,818,2851|
977,85,1048|
885,326,5651|
161,221,1678|
121,67,4726|
920,155,4634|
254,666,9452|
910,864,9845|
906,82,323|
535,268,4956|
738,393,3078|
593,566,6835|
717,687,612|
739,362,9887|
874,216,1762|
1000,944,3274|
303,510,627|
533,721,9298|
298,647,993|
829,10,6842|
405,743,8048|
672,893,9943|
973,886,8180|
851,203,6580|
937,144,1712|
663,531,5487|
763,495,2684|
747,427,2170|
768,816,1237|
734,160,6667|
392,553,72|
935,706,316|
917,610,8689|
961,296,1067|
987,234,96|
27,159,9179|
629,845,7156|
624,303,8817|
861,202,3405|
606,738,6585|
725,911,9088|
206,261,7711|
819,382,9364|
348,413,219|
946,194,6069|
460,922,1924|
264,241,4356|
376,984,6963|
363,417,1685|
502,950,3985|
121,23,1440|
449,259,2177|
971,157,6833|
999,485,4697|
704,556,6344|
825,364,508|
387,904,5481|
436,201,265|
652,894,8765|
839,501,391|
93,636,467|
443,882,9978|
620,173,4784|
367,710,9247|
588,795,6563|
711,380,71|
877,946,6081|
341,378,1965|
948,637,1927|
490,762,448|
979,597,1796|
827,660,9345|
799,73,3003|
786,980,1190|
394,279,783|
172,583,3709|
296,656,769|
170,642,8861|
532,35,1052|
676,48,6161|
343,809,842|
90,76,8038|
337,639,2564|
864,668,2910|
922,933,1686|
984,847,3120|
286,312,1857|
859,34,1654|
677,83,2823|
729,789,1021|
466,315,2418|
481,753,2616|
474,940,7565|
392,670,9310|
271,893,602|
726,90,9272|
963,422,346|
79,56,9636|
793,831,5592|
32,557,8372|
749,758,7375|
689,131,4367|
318,128,8559|
970,234,3695|
19,308,1516|
687,5,18|
610,327,2623|
452,745,9657|
903,209,2195|
305,374,172|
542,282,3768|
146,600,3860|
604,128,3348|
641,856,1615|
718,503,2765|
381,423,6432|
270,569,7361|
742,478,5436|
547,224,2174|
793,357,8990|
215,867,7610|
634,784,1524|
42,170,2989|
215,32,1163|
116,416,1265|
651,80,9415|
630,141,889|
750,846,881|
741,968,199|
627,358,1031|
370,182,1250|
943,138,1392|
718,39,8316|
289,253,9830|
944,611,7503|
786,176,6338|
979,130,322|
931,154,6307|
642,98,2876|
345,430,4539|
515,349,505|
888,409,1424|
300,613,4746|
674,905,3052|
429,764,6659|
48,882,4061|
551,1000,3212|
966,306,696|
461,732,5904|
155,699,211|
514,550,5697|
780,282,3723|
294,398,946|
334,287,8719|
656,575,6108|
976,624,8347|
366,861,8346|
385,844,7813|
209,134,9389|
464,21,5448|
965,565,120|
307,116,7760|
108,144,1|
673,650,1147|
256,731,8558|
55,114,1409|
109,696,8853|
342,765,2841|
323,148,218|
659,552,6633|
126,250,6638|
277,460,8577|
697,119,9572|
953,187,5608|
315,322,4081|
967,264,3017|
532,245,4583|
253,889,2897|
199,292,5071|
207,25,558|
510,468,8421|
464,458,883|
341,204,9945|
58,867,261|
924,605,722|
248,694,3648|
913,910,2000|
616,934,4124|
932,178,3560|
609,166,8312|
68,746,140|
711,812,2927|
71,734,6623|
105,929,7342|
437,865,4874|
551,296,463|
909,467,3861|
213,30,6498|
677,706,6543|
564,876,7142|
188,827,2476|
129,625,442|
179,23,3381|
192,412,236|
737,140,769|
380,269,3830|
529,240,5708|
614,951,5803|
159,837,3760|
195,927,1049|
421,879,2151|
609,467,666|
723,714,5198|
235,749,9934|
679,375,8790|
593,214,8292|
408,311,7938|
17,982,4773|
216,302,278|
636,208,3986|
107,278,8955|
223,568,8433|
982,515,152|
849,186,636|
473,372,5402|
929,108,9121|
204,712,9909|
479,176,37|
987,5,227|
192,108,1799|
805,442,1614|
86,548,2168|
142,388,1681|
969,645,1236|
754,531,4144|
821,871,557|
317,275,7290|
487,408,969|
314,591,3437|
974,438,8994|
766,433,9006|
486,389,1076|
202,178,7444|
776,110,8376|
507,664,4573|
181,695,3774|
852,106,9752|
939,978,5809|
527,135,893|
362,186,496|
547,935,9480|
300,28,3501|
391,469,2994|
789,248,8462|
530,644,1447|
669,455,8797|
483,784,636|
3,613,3257|
92,887,4117|
501,234,4147|
490,715,5010|
28,589,4705|
210,3,8003|
647,832,69|
165,797,1130|
402,618,9609|
583,994,7329|
376,78,770|
651,959,4564|
334,936,3472|
412,754,666|
516,395,492|
730,361,7712|
649,597,1608|
59,164,4758|
914,716,1411|
85,975,8720|
432,224,802|
233,275,121|
562,306,1682|
621,930,3765|
790,428,6511|
606,327,9692|
713,855,3021|
542,111,5839|
446,485,8560|
185,457,3535|
101,624,9460|
796,231,5216|
228,412,1861|
56,347,7785|
972,770,3656|
737,791,8600|
33,967,5505|
240,179,1340|
374,955,4410|
499,145,2937|
503,95,6563|
341,797,8695|
637,744,6508|
105,683,7139|
773,961,4397|
147,505,7213|
332,453,2575|
540,657,3880|
461,301,1824|
915,692,9854|
489,515,5122|
874,335,7673|
810,579,1308|
956,965,6090|
645,701,3368|
626,338,694|
667,85,2164|
966,252,932|
232,933,945|
477,40,6897|
974,198,9895|
477,117,492|
590,286,79|
898,340,3994|
484,528,6919|
265,54,2963|
621,634,1224|
560,829,1157|
750,730,8005|
540,74,562|
77,65,2955|
156,6,7325|
968,84,6850|
851,828,6642|
813,841,7052|
153,390,712|
414,7,319|
318,370,3773|
180,753,5365|
938,783,309|
669,848,9548|
735,157,6538|
654,547,487|
792,537,966|
36,880,451|
567,165,8267|
248,471,6627|
561,724,2108|
668,510,381|
418,396,122|
370,135,2843|
594,355,218|
826,687,7219|
752,439,8078|
365,239,64|
760,352,1150|
684,236,7774|
811,820,4402|];